package com.搜索和回溯;

import java.util.ArrayList;

class Solution8 {
    //法一:将root.val添加到ArrayList中
    ArrayList arr=new ArrayList();
    public int kthLargest(TreeNode root, int k) {
        dfs(root);
        int len=arr.size();
        int res= (int) arr.get(len-k);
        return res;
    }
    void dfs(TreeNode root){
        if(root==null) return;
        dfs(root.left);
        arr.add(root.val);
        dfs(root.right);
    }
    //法二：求 “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”。
    int res,k;
    public int kthLargest2(TreeNode root, int k) {
        this.k=k;
        dfs2(root,this.k);
        return res;
    }
    void dfs2(TreeNode root,int k){
        if(root==null || k==0) return;
        dfs(root.right);
        if(--k==0) res=root.val;
        dfs(root.left);
    }
}

public class 剑指Offer54二叉搜索树的第k大节点 {
    public static void main(String[] args) {

    }
}
